package main

import "fmt"

func main() {
	arr := []int{3, 2, 4, 9, 3, 2, 9, 4}

	heLanSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

func heLanSort(arr []int, L, R int) {

	p1 := L - 1
	p2 := R

	for i := 0; i < len(arr); i++ {

		if i == p2 {
			break
		}
		if arr[i] < arr[R] {
			p1++
			arr[i], arr[p1] = arr[p1], arr[i]

		} else if arr[i] == arr[R] {

			p1++
		} else if arr[i] > arr[R] { //大于index这个数的时候大的这个数就被调换到>区了，换过来的数没有经过判断所以要让i--让其重新判断一下要不然没判断过就跳走会出问题
			p2--
			arr[p2], arr[i] = arr[i], arr[p2]
			i--
		}
	}
	arr[p2], arr[R] = arr[R], arr[p2]

}
